package gold.digger;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LCIT1614 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        /**
         * y = (y2 - y1) / (x2 - x1) * x + b
         * (y2 - y1) * x - (x2 - x1) * y + c = 0;
         * (y2 - y1) * x1 - (x2 - x1) * y1 + c = 0;
         * ax + by + c = 0;
         * a = y2 - y1
         * b = x1 - x2
         * c = (x2- x1) * y1 - (y2 - y1) * x1
         */
        public int[] bestLine(int[][] points) {
            Map<String, int[]> map = new HashMap<>(); // key:a_b_c value:[1][2]分别记录起始值 [3]记录长度
            String key_max = null; // 记录最长的对应的key
            int max = 0;
            int length = points.length;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    int x1 = points[i][0], x2 = points[j][0], y1 = points[i][1], y2 = points[j][1];
                    int a = y2 - y1;
                    int b = x1 - x2;
                    int c = (x2 - x1) * y1 - (y2 - y1) * x1;
                    if (a < 0) {
                        a = -a;
                        b = -b;
                        c = -c;
                    }
                    int gcd = gcd(gcd(a, b), c);
                    // 记录到map中 以a_b_c来归类
                    String key = String.format("%d_%d_%d", a / gcd, b / gcd, c / gcd);
                    int[] value;
                    if (map.get(key) == null) {
                        value = new int[]{i, j, 1};
                        map.put(key, value);
                    } else {
                        value = map.get(key);
                        value[2]++;
                        if (key.equals(key_max))
                            max++;
                    }
                    // 更新最值
                    if (value[2] > max) {
                        key_max = key;
                        max = value[2];
                    }
                    // 如果与最大值相等, 取小值
                    if (value[2] == max) {
                        int[] oldMaxValue = map.get(key_max);
                        if (value[0] < oldMaxValue[0] || (value[0] == oldMaxValue[0] && value[1] < oldMaxValue[1])) {
                            key_max = key;
                            max = value[2];
                        }
                    }
                }
            }
            int[] value = map.get(key_max);
            return new int[]{value[0], value[1]};
        }

        /**
         * 最大公约数
         */
        public int gcd(int x, int y) {
            return y == 0 ? x : gcd(y, x % y);
        }
    }

    public void run() {
        Solution solution = new Solution();
    }

    public static void main(String[] args) throws Exception {
        LCIT1614 an = new LCIT1614();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
